package slru

import (
	"gitee.com/sunny-zhangqiang/zcache/comm/list"
	"sync"
)

// modified from github.com/dgryski/go-memcache.
// add maxBytes limit.
// add exist function.

type sLruItem struct {
	lidx  int
	key   string
	value interface{}
}

// S4LRU  implements the 4-segmented LRU caching algorithm
type S4LRU struct {
	sync.Mutex
	maxEntries int
	maxBytes   int
	valueSize  func(interface{}) int

	data      map[string]*list.Element
	lists     []*list.List
	byteSizes []int
}

// New returns a new S4LRU cache that with the given maxEntries and maxBytes.  Each of the
// lists will have 1/4 of the capacity.
func New(maxEntries, maxBytes int, valueSize func(interface{}) int) *S4LRU {
	maxEntries, maxBytes = maxEntries/4, maxBytes/4
	if maxBytes > 0 && valueSize == nil {
		panic("valueSize should be configured when maxBytes > 0")
	}

	return &S4LRU{
		maxEntries: maxEntries,
		maxBytes:   maxBytes,
		valueSize:  valueSize,
		data:       make(map[string]*list.Element, maxEntries*4),
		lists:      []*list.List{list.New(), list.New(), list.New(), list.New()},
		byteSizes:  make([]int, 4),
	}
}

func (s *S4LRU) isListFull(idx int) bool {
	if s.maxEntries > 0 && s.lists[idx].Len() >= s.maxEntries {
		return true
	}
	if s.maxBytes > 0 && s.byteSizes[idx] >= s.maxBytes {
		return true
	}
	return false
}

func (s *S4LRU) itemByteSize(key string, value interface{}) int {
	if s.maxBytes > 0 {
		return len(key) + s.valueSize(value)
	}
	return 0
}

func (s *S4LRU) Exist(key string) bool {
	s.Lock()
	defer s.Unlock()
	_, ok := s.data[key]
	return ok
}

// Get returns a value from the cache
func (s *S4LRU) Get(key string) (interface{}, bool) {
	s.Lock()
	defer s.Unlock()

	v, ok := s.data[key]

	if !ok {
		return nil, false
	}

	item := v.Value.(*sLruItem)
	itemSize := s.itemByteSize(item.key, item.value)

	// already on final list?
	if item.lidx == len(s.lists)-1 {
		s.lists[item.lidx].MoveToFront(v)
		return item.value, true
	}

	// is there space on the next list?
	if !s.isListFull(item.lidx + 1) {
		// just do the remove/add
		s.lists[item.lidx].Remove(v)
		s.byteSizes[item.lidx] -= itemSize

		item.lidx++
		s.data[key] = s.lists[item.lidx].PushFront(item)
		s.byteSizes[item.lidx] += itemSize
		return item.value, true
	}

	// no free space on either list, so we do some in-place swapping to avoid allocations
	// the key/value in bitem need to be moved to the front of c.lists[item.lidx]
	// the key/value in item need to be moved to the front of c.lists[bitem.lidx]
	back := s.lists[item.lidx+1].Back()
	bitem := back.Value.(*sLruItem)
	bitemSize := s.itemByteSize(bitem.key, bitem.value)

	// update byte sizes.
	diff := itemSize - bitemSize
	s.byteSizes[item.lidx] -= diff
	s.byteSizes[item.lidx+1] += diff

	// swap the key/values
	bitem.key, item.key = item.key, bitem.key
	bitem.value, item.value = item.value, bitem.value

	// update pointers in the map
	s.data[item.key] = v
	s.data[bitem.key] = back

	// move the elements to the front of their lists
	s.lists[item.lidx].MoveToFront(v)
	s.lists[bitem.lidx].MoveToFront(back)

	return bitem.value, true
}

// Set sets a value in the cache
func (s *S4LRU) Set(key string, value interface{}) {
	s.Lock()
	defer s.Unlock()

	itemSize := s.itemByteSize(key, value)

	if !s.isListFull(0) {
		s.data[key] = s.lists[0].PushFront(&sLruItem{0, key, value})
		s.byteSizes[0] += itemSize
		return
	}

	// reuse the tail item
	e := s.lists[0].Back()
	item := e.Value.(*sLruItem)

	delete(s.data, item.key)
	s.byteSizes[0] -= s.itemByteSize(item.key, item.value)
	s.byteSizes[0] += itemSize

	item.key = key
	item.value = value
	s.data[key] = e
	s.lists[0].MoveToFront(e)
}

// Entries returns the total number of items in the cache
func (s *S4LRU) Len() int {
	s.Lock()
	defer s.Unlock()

	return len(s.data)
}

// Size returns the total byte size in the cache
func (s *S4LRU) Size() int {
	s.Lock()
	defer s.Unlock()

	bs := s.byteSizes
	return bs[0] + bs[1] + bs[2] + bs[3]
}

// Remove removes an item from the cache, returning the item and a boolean indicating if it was found
func (s *S4LRU) Remove(key string) (interface{}, bool) {
	s.Lock()
	defer s.Unlock()

	v, ok := s.data[key]

	if !ok {
		return nil, false
	}

	item := v.Value.(*sLruItem)

	s.lists[item.lidx].Remove(v)
	s.byteSizes[item.lidx] -= s.itemByteSize(key, item.value)

	delete(s.data, key)

	return item.value, true
}
